<?php
/**
 * Print all edge nodes of a complete binary tree anti-clockwise.
 * That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.
 * In other words, print the boundary of the tree.
 */

require_once 'util.php';

importJS();

$arr = generateRandomArray(1, 99, 7);
$value1 = $arr[3];
$value2 = $arr[5];

var_dump($arr);

$root = null;
foreach( $arr as $value ){
	$root = bst_insert($value, $root);
}

//bt_print_inorder($root);
//bt_draw($root);
bt_draw( $root );

echo "<br/>";

/*
// Current most left/right node
$left = $root;
$right = $root;

$leaves = array();
$lefts = array();
$rights = array();

printLeaveRecursive( $root, $root, $left, $right, $lefts, $rights, $leaves );

echo $root->value. " ";

foreach( $lefts as $node ){
	echo $node->value. " ";
}

foreach( $leaves as $node ){
	echo $node->value. " ";
}

while( $node = array_pop( $rights ) ){
	echo $node->value. " ";
}
*/

printBoundary( $root );

// Solution 1:
// Use 3 different stacks to store left edge, right edge and all the leaves.
function printLeaveRecursive( $node, $root, &$left, &$right, &$lefts, &$rights, &$leaves ){

	if( !$node ){
		return;
	}

	if( $node->left ){
		// Update the left most node
		if( $node == $left ){
			if( $node->left ){
				$left = $node->left;
				array_push( $lefts, $left );
			}
		}
		printLeaveRecursive( $node->left, $root, $left, $right, $lefts, $rights, $leaves );
	}
	
	if( $node->right ){
		// Update the right most node
		if( $node == $right ){
			if( $node->right ){
				$right = $node->right;
				array_push( $rights, $right );	
			}
		}
		printLeaveRecursive( $node->right, $root, $left, $right, $lefts, $rights, $leaves );
	}

	if( !$node->left && !$node->right ){
		// No child, this is a leave, push if not left or right most leave
		if( $node != $left && $node != $right && $node != $root ){
			array_push( $leaves, $node );
		}
	}

	return;
}

// Solution 2:
// Better solution without any memory requirement...
// Key point is passing a flag stating if is on edge.
// On the left half is a straight preoder
// On the right half, we need a postorder traverse
function printLeftEdge( $node, $isEdge ){
	if( !$node ){
		return;
	}

	// Print if on edge or is a leave
	if( $isEdge || ( !$node->left && !$node->right ) ){
		echo $node->value." ";
	}

	// Continue
	if( $node->left ){
		printLeftEdge( $node->left, true );
	}
	if( $node->right ) {
		printLeftEdge( $node->right, false );
	}
}

function printRightEdge( $node, $isEdge ){
	if( !$node ){
		return;
	}

	// Print child first on the right half
	if( $node->left ){
		printRightEdge( $node->left, false );
	}
	if( $node->right ) {
		printRightEdge( $node->right, true );
	}

	// Print if on edge or is a leave
	if( $isEdge || ( !$node->left && !$node->right ) ){
		echo $node->value." ";
	}
}

function printBoundary( $root ){
	if( !$root ){
		return;
	}

	echo $root->value." ";

	printLeftEdge( $root->left, true );
	printRightEdge( $root->right, true );

	return;
}